package com.example.linked.doublepointers;

import com.example.linked.ListNode;

/**
 * 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
 *  例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
 *
 *  示例：
 * 给定一个链表: 1->2->3->4->5, 和 k = 2.
 *
 * 返回链表 4->5.
 */
public class Offer22_GetKthFromEnd {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        int res = new Solution().getKthFromEnd(head, 4).val;
        System.out.println(res);

    }

    static class Solution {
        /**
         * 双指针
         * 定义p1, p2两个指针
         * p1指针先移动k步，
         * 然后两指针一起移动，直到p1到尾部
         * 返回p2
         * @param head
         * @param k
         * @return
         */
        public ListNode getKthFromEnd2(ListNode head, int k) {
            ListNode p1 = head;
            ListNode p2 = head;
            // 确定两指针的间距k
            for (int i = 0; i < k; i++) {
                if (p1 != null) p1 = p1.next;
                else return null;// 链表长度不够k，直接返回null
            }

            while (p1 != null) {
                p1 = p1.next;
                p2 = p2.next;
            }
            return p2;
        }

        /**
         * 两次遍历
         * @param head
         * @param k
         * @return
         */
        public ListNode getKthFromEnd1(ListNode head, int k) {
            if (head == null) return null;
            ListNode tmp = head;
            int count = 0;
            while (tmp != null) {
                tmp = tmp.next;
                ++count;
            }

            System.out.println(count);
            if (count >= k) {
                tmp = head;
                for (int i = 0; i < count - k; ++i) {
                    tmp = tmp.next;
                }
                return tmp;
            }
            return null;
        }

        public ListNode getKthFromEnd(ListNode head, int k) {
            return getKthFromEnd2(head, k);
        }
    }
}
